package oj;

import java.util.*;

/**
 oj题155 最小栈：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
 */

/**
 * 方法一：创建两个栈：一个用来正常放置元素一个用来放当前所有元素之中的最小值
 *       如果最小值发生变化，那么将当前最小值更新到最小值栈中
 */
 public class MinStack {
     private Deque<Integer> normalStack = new LinkedList<>();
     private Deque<Integer> minStack = new LinkedList<>();
     //构造方法(无参)
    public MinStack() {

    }

    public  void push(int val) {
        //有四种可能：
        //1.minStack.isEmpty() -> min = val
        //2.!minStack.isEmpty() && val < minStack.peek() -> val入栈
        //3.!minStack.isEmpty() && val > minStack.peek() -> minStack.peek()再一次入栈
        //4.!minStack.isEmpty() && val == minStack.peek() -> val或者minStack.peek()入栈都可以
        int min = val;
        if(!minStack.isEmpty() && val > minStack.peek()){
            min = minStack.peek();
        }
        normalStack.push(val);
        minStack.push(min);
    }

    public void pop() {
        if(normalStack.isEmpty()){
            return;
        }
        normalStack.pop();
        minStack.pop();
    }

    public int top() {
        if(normalStack.isEmpty()){
            return -1;
        }
        return normalStack.peek();
    }

    public int getMin() {
        if(normalStack.isEmpty()){
            return -1;
        }
        return minStack.peek();
    }

    /**
     * 方法二：其余都不变，在判断 !minStack.isEmpty() && val >= minStack.peek();
     * 即在 val 与minStack.peek()相等时，入栈一次
     */

//    public  void push(int val) {
//        //有三种可能：
//        //1.minStack.isEmpty() -> min = val
//        //2.!minStack.isEmpty() && val < minStack.peek() -> val入栈
//        //3.!minStack.isEmpty() && val >= minStack.peek() -> minStack.peek()再一次入栈
//        int min = val;
//        if(!minStack.isEmpty() && val >= minStack.peek()){
//            min = minStack.peek();
//        }
//        normalStack.push(val);
//        minStack.push(min);
//    }
//
//    public void pop() {
//        if(normalStack.isEmpty()){
//            return;
//        }
//        normalStack.pop();
//        minStack.pop();
//    }
//
//    public int top() {
//        if(normalStack.isEmpty()){
//            return -1;
//        }
//        return normalStack.peek();
//    }
//
//    public int getMin() {
//        if(normalStack.isEmpty()){
//            return -1;
//        }
//        return minStack.peek();
//    }


    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(5);
        stack.push(3);
        stack.push(7);
        stack.push(1);
        stack.push(1);
        stack.push(0);

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
    }
}
